package com.nuo.laboratory.dataStructure;

import lombok.Data;

import java.util.Arrays;

/**
 * hash集合 链表数组实现
 *
 * @author LGC
 * @date 2022/3/30 14:55
 */
@Data
public class MyHashSet {
    private static final int size = 100000;
    Node[] nodes = new Node[size];

    public MyHashSet() {

    }

    public void add(int key) {
        if(!contains(key)){
            // 为hash函数
            int hash = key % size;
            Node node = nodes[hash];
            if (node == null) {
                nodes[hash] = new Node(key);
            } else {
                if (node.next == null) {
                    node.next = new Node(key);
                } else {
                    while (node.next != null) {
                        node = node.next;
                    }
                    node.next = new Node(key);
                }
            }
        }

    }

    public void remove(int key) {
        if(!contains(key)){
            int hash = key % size;
            Node node = nodes[hash];
            // 下一个节点
            Node curr = node.next;
            while (curr != null) {
                if (curr.val != key) {
                    node = curr;
                } else {
                    node.next = curr.next;
                }
                curr = curr.next;
            }
        }
    }

    public boolean contains(int key) {
        int hash = key % size;
        Node node = nodes[hash];
        while (node != null) {
            if (node.val == key) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    public static void main(String[] args) {
//        ["MyHashSet","add","add","contains","contains","add","contains","remove","contains"]
//        [[],[1],[2],[1],[3],[2],[2],[2],[2]]
        MyHashSet myHashSet = new MyHashSet();
        System.out.println(Arrays.toString(myHashSet.getNodes()));
        myHashSet.add(1);
        System.out.println(Arrays.toString(myHashSet.getNodes()));
        myHashSet.add(2);
        System.out.println(Arrays.toString(myHashSet.getNodes()));
        System.out.println(myHashSet.contains(1));
        System.out.println(myHashSet.contains(3));
        myHashSet.add(2);
        System.out.println(Arrays.toString(myHashSet.getNodes()));
        System.out.println(myHashSet.contains(2));
        myHashSet.remove(2);
        System.out.println(myHashSet.contains(2));
    }


}

/**
 * 定义简单链表节点
 */
@Data
class Node {
    int val;
    Node next;

    Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }

    public Node(int val) {
        this.val = val;
    }
}
